import java.util.Arrays;

public class ShellSort {

    public static void main(String[] args) {
        int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        shellSortShift(arr);
        System.out.println(Arrays.toString(arr));
    }

    //希尔排序交换位置法
    public static void shellSortSwap(int[] arr) {

        //控制前面的
//        for (int i = 5; i < arr.length; i++) {
//            //控制后面的
//            for (int j = i - 5; j >= 0; j--) {
//                if (arr[j + 5] < arr[j]) {
//                    int temp = arr[j + 5];
//                    arr[j + 5] = arr[j];
//                    arr[j] = temp;
//                }
//            }
//        }
//        System.out.println(Arrays.toString(arr));
//        for (int i = 2; i < arr.length; i++) {
//            //控制后面的
//            for (int j = i - 2; j >= 0; j--) {
//                if (arr[j + 2] < arr[j]) {
//                    int temp = arr[j + 2];
//                    arr[j + 2] = arr[j];
//                    arr[j] = temp;
//                }
//            }
//        }
//        System.out.println(Arrays.toString(arr));
//        for (int i = 1; i < arr.length; i++) {
//            //控制后面的
//            for (int j = i - 1; j >= 0; j--) {
//                if (arr[j + 1] < arr[j]) {
//                    int temp = arr[j + 1];
//                    arr[j + 1] = arr[j];
//                    arr[j] = temp;
//                }
//            }
//        }
//        System.out.println(Arrays.toString(arr));

        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            //控制当前组别的后面临界值
            for (int i = gap; i < arr.length; i++) {

                //控制当前组别前面的临界值
                for (int j = i - gap; j >= 0; j--) {
                    if (arr[j + gap] < arr[j]) {
                        int temp = arr[j + gap];
                        arr[j + gap] = arr[j];
                        arr[j] = temp;
                    }
                }
            }
            //gap = 5
            //i = 5
            //j = 0
            //j+gap = 5

            //i = 6
            //j = 1
            //j+gap = 6


            //gap = 2
            //i = 2
            //j = i-gap = 0
            //j+gap = 2

            //gap = 2
            //i = 3
            //j = i-gap = 1
            //j+gap = 3
            //3和1比较
            //j--

            //gap = 2
            //i = 3
            //j = 0
            //j+gap = 2
            //2和0比较

            //System.out.println(Arrays.toString(arr));
        }
    }

    //移位法
    public static void shellSortShift(int[] arr) {
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            //控制当前组别的后面临界值 当前数
            for (int i = gap; i < arr.length; i++) {
                //提取当前数
                int temp = arr[i];

                //System.out.println("i=" + i + "   temp=" + temp);
                //寻找前面的数
                int j = i;
                if (arr[j] < arr[j - gap]) {
                    //j-gap 防止索引越界
                    //temp < arr[j - gap] 如果当前数小于前面的数就进行移位操作
                    while (j - gap >= 0 && temp < arr[j - gap]) {
                        arr[j] = arr[j - gap];
                        //迭代 向前扫描
                        j -= gap;
                    }
                    //当前数归位
                    arr[j] = temp;
                }
            }
        }
    }
}
